/* If both aliases have two names and both names are really far apart then don't make them be the same person */

#include <QString>
#include <QStringList>
#include <QList>
#include <QFile>
#include <QtDebug>
#include <QRegExp>
#include <QSet>
#include <QtAlgorithms>
#include <QTextStream>
#include <iostream>
#include <editdistance.h>

/* blacklist regular expression, believe it or not, there are a bunch of paypals! */
#define BLACKLISTRE "(mailing)?lists?|admin(istrator)?|webmaster|apache|support|postmaster|(un)?subscribe|dev|root|info|httpd|archive|mail(er)?|daemon|paypal|the|postgres?(ql)?|pgsql|hackers|lists?|python|dev|mysql"

float max(float a, float b) {
	return a > b ? a : b;
}

float min(float a, float b) {
	return a < b ? a : b;
}

using namespace std;

typedef struct Alias {
	QString email; /* original email */
	QString name; /* original name */
	QString nemail; /* normalized versions */
	QString nname;
	QString emailBase; /* email address up to the @ */
	QSet<struct Alias *> *set; /* for building clusters */
	QList<struct Alias *> *matchList;
	bool flag;
} Alias;

typedef QList<Alias *> AliasList;

/* reads the output of sql statement on aliases table using psql 
   The command to create the aliases file needed is:
   
*/
AliasList *readAliasesFromFile(QString filename)
{
	qDebug() << "Reading " << filename;
	AliasList *aliasList = new AliasList();
	Alias *alias;
	QFile file(filename);
	file.open(QIODevice::ReadOnly | QIODevice::Text);
	char buf[1024];
	qint64 lineLength;
	QString record;
	QStringList stringList;

	int num=100000;

	while (!file.atEnd()) {
		
		lineLength = file.readLine(buf, sizeof(buf));
		record = buf;
		//qDebug() << record;
		if (!record.contains("|"))
			continue;
		stringList = record.split("|", QString::SkipEmptyParts);
		alias = new Alias();
		alias->email = stringList[0].trimmed();
		alias->name = stringList[1].trimmed();
		alias->set = new QSet<Alias *>();
		alias->set->insert(alias);
		alias->matchList = new QList<Alias *>();
		//qDebug() << "name is " << alias->name << endl;
		aliasList->append(alias);
		if (num-- == 0)
			break;	
	}
	qDebug() << "done";
	return aliasList;
}

		
/* I want the list sorted with the highest numbers first */
bool setSizeLessThan(const QSet<Alias *> *s1, const QSet<Alias *> *s2) {
	return s1->size() > s2->size();
}

/* for sorting lists of aliases */
bool aliasLessThan(const Alias *a1, const Alias *a2) {
	return a1->email < a2->email;
}

void writeClusterDotFile(QSet<Alias *> *set, QString filename) {
	QFile dotFile(filename);
	dotFile.open(QFile::WriteOnly);
	QTextStream dotStream(&dotFile);

	dotStream << "strict digraph cluster {\n";
	foreach(Alias *alias1, *set) {
		foreach(Alias *alias2, *alias1->matchList) {
			dotStream << "\"" + alias1->email + ":" + alias1->name + "\"" << " -> " << "\"" + alias2->email + ":" + alias2->name + "\"\n";
		}
	}
	dotStream << "}\n";
	
		
	dotFile.close();
}
	
			
void printClusters(AliasList *aliasList, QTextStream &clusterStream) {
	qDebug() << "Printing Clusters";
	foreach(Alias *alias, *aliasList) {
		alias->flag = false;
	}

	QList< QSet<Alias *> *> *clusterList = new QList< QSet<Alias *> *>();
	
	foreach(Alias *alias, *aliasList) {
		if (alias->flag == true)
			continue;
		clusterList->append(alias->set);
		/* mark each alias in this cluster as being visited so we don't include the 
		 * same cluster twice
		 */
		foreach (Alias *setAlias, *(alias->set)) {
			setAlias->flag = true;
		}
	}
	
	/* sort the clusters into order by size with the largest ones coming first 
	 */
	qSort(clusterList->begin(), clusterList->end(), setSizeLessThan);

	int i = 1;
	foreach (QSet<Alias *> *set, *clusterList) {
		clusterStream << "=== Cluster " << i << "(" << set->size() << ") ===\n";
		QList<Alias *> aliasCluster = set->toList();
		qSort(aliasCluster.begin(), aliasCluster.end(), aliasLessThan);
		foreach (Alias *alias, aliasCluster) {
			clusterStream << alias->email + ":" + alias->name + "\n";
		}
		writeClusterDotFile(set, QString("cluster%1.dot").arg(i));
		i++;
		
	}
}
	
/* return edit distance as a ratio of edits to length of the longer string (1.0 means strings are the same, lower is worse)*/
float editDistanceRatio(QString &s1, QString &s2) {
	float distance = editDistance((const char *)s1.toAscii(), (const char *)s2.toAscii());
	float maxLength = max(s1.length(), s2.length());
	return (maxLength - distance) / maxLength;
}

/* compare two names to each other */
float compareNames(QString a, QString b)
{
	float score = 0.0;
	/* if both names are empty, we don't want that to be a perfect match */
	if (a.length() == 0 || b.length() == 0)
		return 0.0;

	if (a == b)
		return 1.0;
	
	/* if one name has at least two parts and is longer than 10 characters and is a substring
	 * of the other, then we want them in the same cluster
	 */
	if (a != b && a.length() >= 10 && a.count(" ") > 0 && b.contains(a)) {
		//qDebug() << "substring10" << a << b;
		return 1.0;
	}
	if (a != b && b.length() >= 10 && b.count(" ") > 0 && a.contains(b)) { 
		//qDebug() << "substring10" << a << b;
		return 1.0;
	}

	/* look at the edit distance on both strings */
	score = max(score, editDistanceRatio(a, b));

	/* if both strings have at least two components to them */
	if (a.count(" ") > 0 && b.count(" ") > 0) {
		QStringList ap = a.split(" "), bp = b.split(" ");
		
		/* take the lower of the editDistanceRatio's
		 * so that andy smith looks like andrew smith, but john smith doesn't look like john doe
		 * that way, both components must match closely
		 */
		score = max(score, 
				min(
					editDistanceRatio(ap.first(), bp.first()), 
					editDistanceRatio(ap.last(), bp.last())
				)
			);
		
		/* if the "ends" match then we want them in the same cluster */
		if (ap.size() != bp.size() && ap.first() == bp.first() && ap.last() == bp.last()) {
			//qDebug() << "ends match!" << a << b;
			score = max(score, .99);
		}

		//If both names have 2 parts and the first names match, but the last names don't, then they are not the same
		if (ap.size() == 2 && bp.size() == 2 && ap[0] == bp[0] && ap[1] != bp[1]) {
			return -1.0;
		}
	}
	return score;
}

/* compare a name from one alias to an email address of another alias */
float compareNameEmail(QString name, QString email) {
	float score = 0.0;
	/* if they're both empty then skip this */
	if (name == "" || email == "")
		return 0.0;

	if (name.count(" ") > 0) {
		QStringList parts = name.split(" ");
		QString first = parts.first();
		QString last = parts.last();
		/* if the email address contains the first and last part of
		 * the name and both parts are at least 2 characters then we'll
		 * say that it's a close match */
		if (first.length() > 1 && last.length() > 1 && 
			email.contains(first) && email.contains(last)) {
			//qDebug() << "whole first and last" << email << name;
			return .98;
			score = max(score, .98);
		}


		/* check for birdc, cbird, chrisb, and bchris
		 * now check for first character of last name and whole first name and
		 * vice versa 
		 */
		if (first.length() > 2 && (email.contains(first + last[0]) || email.contains(last[0] + first))) {
			score = max(score, .95);
			//qDebug() << "firstlast1" << email << name;
		}
		if (last.length() > 2 && (email.contains(first[0] + last) || email.contains(last + first[0]))) {
			score = max(score, .95);
			//qDebug() << "first1last" << email << name;
		}
	}
	return score;
}


QString normalizeName(QString name)
{
	if (name == "")
		return name;
	QString origName = name;
	/* remove jr. */
	static QRegExp jrRe("[, ]*jr[. ]");
	/* remove all punctuation */
	static QRegExp puncRe("[,.-]*");
	/* turn all sequences of spaces into one space */
	static QRegExp spaceRe(" [ ]+");
	/* remove common useless words like admin, lists, support, etc. */
	static QRegExp commonRe(BLACKLISTRE);

	/* if the name contains exactly one comma then remove the comma and switch the two
	 * sides so "bird, chris" becomes "chris bird" */
	name = name.replace(jrRe, "");
	if (name.count(',') == 1) {
		QStringList l = name.split(',');
		/* only do this if there is one word before the comma "bird, christian a." to "christian a. bird", but "paul jones, the contractor" doesn't get changed */
		if (l[0].trimmed().count(" ") == 0){
			name = l[1] + " " + l[0];
		}
	}
	name = name.replace(commonRe, "").replace(puncRe, "").replace(spaceRe, " ").trimmed();
	//if (origName != name)
	//	qDebug() << "changed from" << origName << "to" << name;
	return name;

}

/* just remove the blacklist terms from the email */
QString normalizeEmail(QString email)
{
	static QRegExp commonRe(BLACKLISTRE);
	static QRegExp puncRe("[,.-]*");
	email = email.replace(commonRe, "").replace(puncRe, "").trimmed();
	return email;
}

int main(int argc, char *argv[]){

    
	AliasList *aliasList;
    if(argc >= 2)
    {
	    aliasList = readAliasesFromFile(argv[1]);
    }
    else
    {
        qDebug() << "Please pass in the file containing the aliases";
        return 1;
    }
	QString emailBase1, emailBase2;
	float score, nameScore, emailNameScore, emailScore;
	int comparisons = 0;
	int pairs = 0, imperfectPairs = 0;
	int total = aliasList->size() * aliasList->size() / 2;
	qDebug() << "There are a total of" << aliasList->size() << "unique aliases";
	qDebug() << "Need to make a total of" << total << "comparisons";
		

	QTextStream pairStream(new QFile("pairs"));
	pairStream.device()->open(QIODevice::WriteOnly);
	
	QTextStream imperfectPairStream(new QFile("imperfectPairs"));
	imperfectPairStream.device()->open(QIODevice::WriteOnly);

	QSet<QString> nameSet;
	QSet<QString> nnameSet;
	int nonempty = 0;
	int empty = 0;

	/* normalize names, email addresses, and grab off the email base (everything before the @) */
	foreach(Alias *alias, *aliasList)
	{
		if (alias->name.trimmed() != "")
			nonempty++;
		else
			empty++;
		alias->nname = normalizeName(alias->name);
		alias->nemail = normalizeEmail(alias->email);
		//emailbase is everything before the @ sign
		alias->emailBase = alias->nemail.left(alias->nemail.indexOf('@'));
		nameSet << alias->name;
		nnameSet << alias->nname;
	}

	qDebug() << "There are a total of" << nonempty << "nonempty names and" << empty << "empty names in the list of aliases.";
	qDebug() << "Before normalization there are" << nameSet.size() << " names and afterwards there are " << nnameSet.size();

	int i = 0, j;
	/* compare each alias to every alias after it in the list */
	foreach(Alias *alias1, *aliasList)
	{
		i++;
		j = 0;
		foreach(Alias *alias2, *aliasList)
		{
			/* this setup here is so that we only compare aliases ahead of alias1 in the list.
			 * still not the most efficient, but oh well... 
			 */
			j++;
			if (j <= i)
				continue;
			/* initialize scores */
			nameScore = emailScore = emailNameScore = 0.0;
			/* show progress */
			comparisons++;
			if (comparisons % 10000 == 0) {
				qDebug() << "compared" << comparisons << "pairs" << "(" << (100 * float(comparisons)) / float(total) << "%)";
			}
			
			nameScore = compareNames(alias1->nname, alias2->nname);
			/* compare both sets of names and emails */
			if (nameScore != 1.0) {
				emailNameScore = max(compareNameEmail(alias1->nname, alias2->nemail),
					compareNameEmail(alias2->nname, alias1->nemail));
			}
			
			
			/*if the email bases match then I think they should be together */
			if (nameScore != 1.0 && emailNameScore < .9 && alias1->emailBase.length() > 2 && alias1->emailBase == alias2->emailBase) {
				emailScore = .94; //editDistanceRatio(alias1->emailBase, alias2->emailBase);
				//qDebug() << "emailbases match";
			}

			

			score = max(nameScore, max(emailScore, emailNameScore));
			
			if (nameScore == -1.0 && alias1->emailBase == alias2->emailBase) {
				qDebug() << "Found one";
				score = 0;
			}
				
			/* this is somewhat arbitrary, but seems to yield good results */
			if (score > .93) {
				pairs++;
				if (score != 1.0) {
					imperfectPairs++;
					imperfectPairStream << score << " | " << alias1->email << " " << alias1->name << " | " << alias2->email << " " << alias2->name << "\n"; 
				} else {
					pairStream << score << " | " << alias1->email << " " << alias1->name << " | " << alias2->email << " " << alias2->name << "\n"; 
				}
					
				//qDebug() << "(" << score << alias1->email + ":" + alias1->name << alias2->email + ":" + alias2->name << ")";
				
				/* Merge the "clusters" we have for each alias
				 * union the sets associated with each alias into the set for alias1 and reassign the sets for all aliases in alias2's set */
				alias1->set->unite(*alias2->set);
				foreach (Alias *a, *alias2->set) {
					a->set = alias1->set;
				}
				alias1->matchList->append(alias2);
			}
		}
	}

	pairStream.device()->close();
	imperfectPairStream.device()->close();

	qDebug() << "Found" << pairs << "pairs\n";
	qDebug() << "Found" << imperfectPairs << "imperfect pairs\n";
	QFile clusterFile("clusteroutput");
	clusterFile.open(QFile::WriteOnly);
	/* write out the data */
	QTextStream clusterStream(&clusterFile);
	printClusters(aliasList, clusterStream);
}


	
